package com.linyaonan.leetcode.sword_to_offer._53_2;

/**
 * 一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
 *
 *  
 *
 * 示例 1:
 *
 * 输入: [0,1,3]
 * 输出: 2
 * 示例 2:
 *
 * 输入: [0,1,2,3,4,5,6,7,9]
 * 输出: 8
 *  
 *
 * 限制：
 *
 * 1 <= 数组长度 <= 10000
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/que-shi-de-shu-zi-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class Solution {

    /**
     * 正常情况下0~n-1,正好存放在长度为n从0开始的递增数列，如果其中只缺少一个数字那么int[i] != i
     * @param nums
     * @return
     */
    public int missingNumber(int[] nums) {
        // 那么一定是后面的数据有问题
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i) {
                return i;
            }
        }
        // 前面都正确，那么排序正确，缺少最后一个n直接返回
        return nums[nums.length - 1] + 1;
    }

    /**
     * 思路二：二分法也是ok的，因为本时的数组是有序的，所以中间节点是否为非指定位置的，如果正常，那么只能是右边异常，否则左边
     */
    public int missingNumber2(int[] nums) {
        if (nums[0] != 0) {
            return 0;
        }
        if (nums[nums.length - 1] == nums.length - 1) {
            return nums[nums.length - 1] + 1;
        }
        // 表示必然存在在内部
        int l = 0;
        int r = nums.length - 1;

        while (l < r) {
            int m = l + ((r - l) >> 1);
            if (nums[m] > m) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return l;
    }
}